package anthology.daily_question._24_10;

import java.util.Arrays;

//https://leetcode.cn/problems/maximum-total-reward-using-operations-i/description/?envType=daily-question&envId=2024-10-25
public class _3180执行操作可获得的最大总奖励1 {
    class Solution {
        public int maxTotalReward(int[] rewardValues) {
            Arrays.sort(rewardValues);
            int m = rewardValues[rewardValues.length - 1];
            int[] dp = new int[2 * m];
            dp[0] = 1;
            for (int x : rewardValues) {
                for (int k = 2 * x - 1; k >= x; k--) {
                    if (dp[k - x] == 1) {
                        dp[k] = 1;
                    }
                }
            }
            int res = 0;
            for (int i = 0; i < dp.length; i++) {
                if (dp[i] == 1) {
                    res = i;
                }
            }
            return res;
        }
    }
}
